#ifndef AllSSPSimple_CPP
#define AllSSPSimple_CPP

#include<limits.h>
#include"AdjacencyList.cpp"

int getMinimum (unsigned int arr[], int visited[], unsigned int num);

class AllSSPSimple
{
    AdjacencyList* list;

private:
    void initializeDistMatrix();

public:
    static const int maxNumberOfNodes = 600;
    void init(AdjacencyList* list);
    int visited[AllSSPSimple::maxNumberOfNodes];
    unsigned int dist[AllSSPSimple::maxNumberOfNodes][AllSSPSimple::maxNumberOfNodes];
    int distMatrixSize;
    AllSSPSimple(AdjacencyList* list);
    AllSSPSimple();
    void computeShortestPath();
    void display();
};

void AllSSPSimple::display()
{
    cout<<"\n\nPrinting min distances"<<endl;
    for (unsigned int i=0; i<this->list->getNumberOfNodes(); i++)
    {
        for (unsigned int j=0; j<this->list->getNumberOfNodes(); j++)
        {
            if (dist[i][j] == std::numeric_limits<unsigned int>::max())
            {
                cout<<"\tInf.";
            }
            else
            {
                cout<<"\t"<<dist[i][j];
            }
        }
        cout<<endl;
    }
}

void AllSSPSimple::computeShortestPath()
{
    initializeDistMatrix();
    for (unsigned int i=0; i<this->distMatrixSize; i++)
    {
        for (unsigned int ii=0; ii<this->distMatrixSize; ii++)
        {
            visited[ii] = 0;
        }
        visited[i] = 1;
        dist[i][i] = 0;
        for (unsigned int j=1; j < this->distMatrixSize; j++)
        {
            int minVertex = getMinimum(dist[i], visited, this->distMatrixSize);
            visited[minVertex] = 1;
            if (dist[i][minVertex] == std::numeric_limits<unsigned int>::max())
            {
                break;
            }
            AdjacencyListNode* temp = this->list->getAdjacencyListNode(minVertex);
            if (temp == NULL)
            {
                continue;
            }
            QueueNode<AdjacencyNode>* temp1 = temp->adjacentNodes.getHead();
            while (temp1 != NULL)
            {
                AdjacencyNode* node = temp1->val;
                if (visited[node->vertex] == 0 && dist[i][node->vertex] > dist[i][minVertex] + node->cost)
                {
                    dist[i][node->vertex] = dist[i][minVertex] + node->cost;
                }
                temp1 = temp1->next;
            }
        }
    }
}

//LinearSearch
int getMinimum (unsigned int arr[], int visited[], unsigned int num)
{
    int min = -1;
    for (unsigned int i=0; i<num; i++)
    {
        if (visited[i] == 0 && (min == -1 || arr[min] > arr[i]))
        {
            min = i;
        }
    }
    return min;
}

void AllSSPSimple::initializeDistMatrix()
{
    QueueNode<AdjacencyListNode>* temp = this->list->adjacencyListImp.getHead();
    while (temp != NULL)
    {
        AdjacencyListNode* node = temp->val;
        unsigned int vertex1 = node->vertex;
        QueueNode<AdjacencyNode>* temp1 = node->adjacentNodes.getHead();
        while (temp1 != NULL)
        {
            AdjacencyNode* node2 = temp1->val;
            unsigned int vertex2 = node2->vertex;
            unsigned int cost = node2->cost;
            dist[vertex1][vertex2] = cost;
            temp1 = temp1->next;
        }
        temp = temp->next;
    }
}

AllSSPSimple::AllSSPSimple(AdjacencyList* list)
{
    this->init(list);
}

AllSSPSimple::AllSSPSimple()
{

}

void AllSSPSimple::init(AdjacencyList* list)
{
    this->list = list;
    this->distMatrixSize = list->getNumberOfNodes();
    for (unsigned int i=0; i<this->distMatrixSize; i++)
    {
        for (unsigned int j=0; j<this->distMatrixSize; j++)
        {
            dist[i][j] = std::numeric_limits<unsigned int>::max();;
        }
    }
}
#endif
